package demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-23
 * Time: 6:55
 */
public class TestDemo1 {


    public static int longestCommonSubsequence(String text1, String text2) {
         if(text1==null||text2==null||text1.length()==0||text2.length()==0){
             return 0;
         }
         char[] str1 = text1.toCharArray();
         char[] str2 = text2.toCharArray();
         return process(str1,str2,text1.length()-1,text2.length()-1);
    }

    public static int process(char[] str1,char[] str2,int i,int j){
        if(i==0&&j==0){
            return str1[i] == str2[j] ? 1 : 0;
        }else if(i==0){//一行
            if (str1[i] == str2[j]) {
                return 1;
            } else {
                return process(str1, str2, i, j - 1);
            }
        }else if(j==0){
            if(str1[i]==str2[j]){
                return 1;
            }else {
                return process(str1,str2,i-1,j);
            }
        }else{
            int p1 = process(str1,str2,i,j-1);
            int p2 = process(str1,str2,i-1,j);
            int p3 = str1[i] == str2[j] ? 1+ process(str1,str2,i-1,j-1) : 0;
            return Math.max(p1,Math.max(p2,p3));
        }
    }

    //改成动态规划
    public static int longestCommonSubsequence1(String text1, String text2) {
        char[] str1 = text1.toCharArray();
        char[] str2 = text2.toCharArray();
        int M = str1.length;
        int N = str2.length;
        int[][] dp = new int[M][N];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        //填写第一行
        for(int i =1;i< N;i++){
            dp[0][i] = str1[0] == str2[i] ? 1 : dp[0][i-1];
        }
        //填写第一列
        for(int j = 1;j<M;j++){
            dp[j][0] = str1[j] == str2[0] ?1 : dp[j-1][0];
        }
        //从左往右填表
        for(int i = 1;i<M;++i){
            for(int j =1;j<N;++j){
                int p1 = dp[i][j-1];
                int p2 = dp[i-1][j];
                int p3 = str1[i] == str2[j] ? 1+ dp[i-1][j-1] : 0;
               dp[i][j] = Math.max(p1,Math.max(p2,p3));
            }
        }
        return dp[M-1][N-1];
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence1("ab12yu567m8",
                "lk1m2j5uu6o7as8"));
    }


}
